1. Field of the Invention
The invention relates to systems such as data base systems and artificial intelligence systems in which relationships between items in an information base such as a data base or a knowledge base are expressed by means of sets of formulas. In a data base system, a formula may express a relationship between fields of different records; for example, the value of a first field may depend on the values of a set of second fields. In a knowledge base system, it may express a logical relationship between two facts in the knowledge base; an example would be that the truth of one of the facts implies the existence of the other.
2. Description of the Prior Art
An area of the prior art which makes particularly wide use of formulas is the "logicist" approach to artificial intelligence. In this type of artificial intelligence, commonsense knowledge is represented by logical formulas and the system "reasons" by doing formal theorem proving using a knowledge base of the logical formulas. For example, if the system's knowledge base indicates that a fact p is true and implies a fact q and the system is presented with a query involving the fact q, the system will infer the truth of the fact q from the knowledge base and will use that inference in answering the query. A general introduction to the knowledge bases used in such systems is Ronald J. Brachman, "The Basics of Knowledge Representation and Reasoning", AT&T Technical Journal, vol. 67, 1, pp. 7-24.
Knowledge bases for artificial intelligence systems employing the logicist approach are written using representation languages which represent the formulas. From the point of view of knowledge base writing, the best representation languages are unrestricted representation languages, which can directly represent any logical formula. A problem with knowledge bases using such unrestricted representation languages is that the complexity of theorem-proving with such knowledge bases is very high--exponential or worse--in both theory and practice. In artificial intelligence systems based on such knowledge bases, the complexity of theorem proving is reflected in the high cost in time and computation resources of answering a query.
One way to make the logicist approach more computationally attractive is to restrict the expressive power of the representation language, so that fast, special-purpose inference algorithms can be employed. But this usually renders the language too limited for practical application (see J. Doyle and R. Patil, "Two Theses of Knowledge Representation: Language Restrictions, Taxonomic Classification, and the Utility of Representation Services", Artificial Intelligence 48(3), 261-298, 1991) and leaves unanswered the question of what to do with formulas that cannot be represented in the restricted form.
As may be seen from the foregoing, there is a trade off in artificial intelligence systems which use the logicist approach between the expressive power of the language used to represent a knowledge base and the computational tractability of the system. It is an object of the invention disclosed herein to alleviate the trade off by permitting use of a general unrestricted representation language while achieving the computational efficiencies possible with restricted representation languages. It is further an object of the invention to alleviate similar trade offs in any information bases employing formulas.